﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    bool isIsomorphic(string s, string t)
    {
        if (s.size() != t.size())
            return false;
        unordered_map<char, char> hash1; // s为键,t为值
        unordered_map<char, char> hash2; // t为键,s为值
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            char ch1 = s[i], ch2 = t[i];
            if (hash1.count(ch1) && hash1[ch1] != ch2 || (hash2.count(ch2) && hash2[ch2] != ch1))
                return false;
            hash1[ch1] = ch2;
            hash2[ch2] = ch1;
        }

        return true;
    }
};

// 最长连续序列
class Solution
{
public:
    int longestConsecutive(vector<int>& nums)
    {
        unordered_map<int, int> hash;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            hash[nums[i]] = i;
        }
        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            int tmp = nums[i];
            // 如果前一个数存在，那么我们就不需要进行再一次的遍历了
            if (hash.count(tmp - 1))
                continue;
            int count = 0;
            while (hash.count(tmp))
            {
                tmp++;
                count++;
            }
            ret = max(ret, count);
        }

        return ret;
    }
};

// 买股票的最佳时期含冷冻期

//处于「买⼊」状态的时候，我们现在有股票，此时不能买股票，只能继续持有股票，或者卖出股票；
//处于「卖出」状态的时候：
//如果「在冷冻期」，不能买⼊；
//如果「不在冷冻期」，才能买⼊
class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        // dp[i][0]:表示第i天结束之后,处于"买入状态"(手中有股票),此时的最大利润
        // dp[i][1]:表示第i天结束之后,处于可交易状态(手中没有股票)
        // dp[i][2]:表示第i天结束之后,处于冷冻期状态
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++)
        {
            // 前一天处于冷冻状态,今天买入或者昨天买入进行啥也不干
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            // 昨天处于冷冻期今天啥也不干,或者昨天处于买入状态,进行卖出
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            // 昨天处于买入状态,今天卖票
            dp[i][2] = dp[i - 1][0] + prices[i];
        }

        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

// 买股票的最佳时期含手续费
class Solution
{
public:
    int maxProfit(vector<int>& prices, int fee)
    {
        int n = prices.size();
        vector<int> f(n + 1);
        auto g = f;
        f[0] = -prices[0];
        // f[i]:表示第i天结束之后，处于买入状态
        // g[i]:表示第i天结束后处于卖出状态
        for (int i = 1; i < n; i++)
        {
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
        }

        return g[n - 1];
    }
};

// 最大子数组和
class Solution
{
public:
    int maxSubArray(vector<int>& nums)
    {
        // dp[i]:表示以i位置为结尾的所有子数组的最大和
        int n = nums.size();
        vector<int> dp(n);
        int ret = INT_MIN;
        dp[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            ret = max(dp[i], ret);
        }

        // 不要忘记了dp[0]
        return max(ret, dp[0]);
    }
};

// 长度最小的子数组
class Solution
{
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int left = 0, right = 0, sum = 0;
        int len = INT_MAX;
        int n = nums.size();
        while (right < n)
        {
            sum += nums[right];
            // 如果减去最左边的还是大于,则需要继续减
            while (sum >= target)
            {
                len = min(len, right - left + 1);
                sum -= nums[left++];
            }
            right++;
        }

        return len == INT_MAX ? 0 : len;
    }
};

class Solution
{
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int n = nums.size();
        int ret = INT_MAX;
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += nums[j];
                if (sum >= target)
                {
                    ret = min(ret, j - i + 1);
                    break;
                }
            }
        }

        return ret == INT_MAX ? 0 : ret;
    }
};

// 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int hash[128] = { 0 };
        int left = 0, right = 0, len = 0;
        int n = s.size();
        while (right < n)
        {
            // 进入窗口
            hash[s[right]]++;
            // 判断
            while (hash[s[right]] > 1)
            {
                hash[s[left]]--;
                left++;
            }
            // 更新结果
            len = max(len, right - left + 1);
            // 让下一个元素进窗口
            right++;
        }

        return len;
    }
};
int main()
{
    return 0;
}